/************************************************************
 * DS_ALGORITHM.HPP                                13.09.2006
 *
 * .
 ************************************************************/

namespace impl {

template <class ITER>
struct TRAITS {
   typedef typename ITER::value_type value_type;
   typedef typename ITER::reference  reference;
};

template <class T>
struct TRAITS<T *> {
   typedef T   value_type;
   typedef T & reference;
};

/*************************************************************
* Sisp()
* 
*************************************************************/
template<class ITER, class CMP>
inline void Sisp(int p, int q, ITER first, const CMP & cmp)
{
   typedef typename TRAITS<ITER>::value_type value_type;

   int i = p, j = i*2;

   value_type x = *(first + i - 1);

   if (j < q && cmp.cmp(*(first + j - 1), *(first + j)) < 0) {
      ++j;
   }

   while (j <= q && cmp.cmp(x, *(first + j - 1)) < 0) {
      *(first + i - 1) = *(first + j - 1);
      
      i = j;
      j = j*2;

      if (j < q &&  cmp.cmp(*(first + j - 1), *(first + j)) < 0) {
         ++j;
      }
   }

   *(first + i - 1) = x;
}

} // namespace impl

/*************************************************************************
* Method: <T>::IsSorted
*
*************************************************************************/
template <class T, class CMP>
inline bool IsSorted(const dsVECTOR<T> & a, const CMP & cmp)
{
   for (int i = 1; i < a.Length(); ++i) {
      if (cmp.cmp(a[i - 1], a[i]) > 0) {
         return false;
      }
   }

   return true;
}

/*************************************************************************
* Method: <T>::IsSorted
*
*************************************************************************/
template <class T, class CMP>
inline bool IsSortedUniq(const dsVECTOR<T> & a, const CMP & cmp)
{
   for (int i = 1; i < a.Length(); ++i) {
      if (cmp.cmp(a[i - 1], a[i]) >= 0) {
         return false;
      }
   }

   return true;
}

/*************************************************************
* Sort()
* 
*************************************************************/
template <class ITER, class CMP>
inline void Sort(ITER first, ITER last, const CMP & cmp_)
{
   // FIXME: run bubble sort for small elements and add checker same as in dsVECTOR::HeapSort
   // to avoid unsorted arrays because incorrect comparator
   // FIXME: support swap
   if (first == last) {
      return ;
   }

#if !defined(_RETAIL) && !defined(_PROFILE)
   dsCHECKED_CMP<CMP> cmp(cmp_);
#else
   const CMP & cmp = cmp_;
#endif

   // Make sure we need sorting
   bool sorted = true;
   for (ITER iter = first; iter + 1 != last; ++iter) {
      if (cmp.cmp(*iter, *(iter + 1)) > 0) {
         sorted = false;
         break;
      }
   }
   if (sorted) {
      return ;
   }

   const int length = (int)(last - first);

   int q = length;
   for (int i = length; i > 0; --i) {
      impl::Sisp(i, length, first, cmp);
   }

   while (q > 1) {
      typename impl::TRAITS<ITER>::value_type x = *first;
      *first = *(first + q - 1);
      *(first + q - 1) = x;

      --q;
      impl::Sisp(1, q, first, cmp);
   }

#ifdef _DEBUG
   for (int k=0; k + 1 < length; ++k) {
      STRONG_ASSERT(cmp.cmp(*(first + k), *(first + k + 1)) <= 0);

      if (cmp.cmp(*(first + k), *(first + k + 1)) > 0) {
         BubbleSort(first, last, cmp);
         return ;
      }
   }
#endif
}

/*************************************************************************
* Method: <ITER, CMP>::BubbleSort
*
*************************************************************************/
template <class ITER, class CMP>
inline void BubbleSort(ITER begin, ITER end, const CMP & cmp)
{
   int length = (int)(end - begin);

   for (int i = 0; i < length - 1; i++) {
      for (int j = i + 1; j < length; j++) {
         if (cmp.cmp(*(begin + j), *(begin + i)) < 0) {
            typename impl::TRAITS<ITER>::value_type x = *(begin + j);
            *(begin + j) = *(begin + i);
            *(begin + i) = x;
         }
      }
   }
}

/*************************************************************
* FindNonSorted()
* 
*************************************************************/
template <class CMP, class ITER, class VAL>
ITER FindNonSorted (const ITER & begin, const VAL & val)
{
   for (ITER it = begin; !it.IsDone(); ++it) {
      if (*it == val) {
         return it;
      }
   }

   return ITER();
}

inline int FindNonSorted(const char * array[], int length, const char * val)
{
   for (int i = 0; i < length; ++i) {
      if (strcmp(array[i], val) == 0) {
         return i;
      }
   }
   return -1;
}

template <class T, class VAL>
int FindNonSorted(const T * array, int length, const VAL & val)
{
   for (int i = 0; i < length; ++i) {
      if (array[i] == val) {
         return i;
      }
   }
   return -1;
}

template <class T, class CMP>
int FindNonSortedMaxIdx(const dsVECTOR<T> & array, const CMP & cmp)
{
   STRONG_ASSERT(array.Length() > 0);

   int idxMax = 0;
   for(int i = 1; i < array.Length(); ++i) {
      if (cmp.cmp(array[i], array[idxMax]) == 1) {
         idxMax = i;
      }
   }
   return idxMax;
}

/***************************************************************
* dsVECTOR::Min ()
*
***************************************************************/
template <class ITER, class CMP>
inline ITER Min(ITER begin, ITER end, const CMP & cmp_)
{
#ifdef _DEBUG
   dsCHECKED_CMP<CMP> cmp(cmp_);
#else
   const CMP & cmp = cmp_;
#endif

   STRONG_ASSERT(end - begin > 0);

   ITER res = begin;
   for (ITER cur = begin + 1; cur != end; ++cur) {
      if (cmp.cmp(*res, *cur) < 0) {
         res = cur;
      }
   }

   return res;
}

/**************************************************************************
* Sort_0_n()                                                              *
*                                                                         *
**************************************************************************/
template <class ITER, class CMP_SWAP_0_N>
inline void Sort_0_n(ITER first, ITER last, const CMP_SWAP_0_N & cmp)
{
   for (ITER iter = first; iter != last; ++iter) {
      int index = cmp.value(iter);
      int counter = 0;
      while (index != iter - first) {
         cmp.swap(iter, first + index);
         index = cmp.value(iter);
         
         STRONG_ASSERT2(counter++ < last - first, counter, last - first);
      }
   }
}

/**************************************************************************
* RemoveDuplicates()                                                      *
*                                                                         *
**************************************************************************/
template <class T, class CMP>
inline int RemoveDuplicates(dsVECTOR<T> & arr, const CMP & cmp)
{
   ds::Sort(arr, cmp);

   int count = 0;
   for (int i = 0, j = 1; j < arr.Length(); j++) {
      if (cmp.cmp(arr[i], arr[j]) == 0) {
         ++count;
         continue;
      }
      i++;
      if (count > 0) {
         dsSwap(arr[i], arr[j]);
      }
   }
   arr.Resize(arr.Length() - count);

   return count;
}

/**************************************************************************
* Reverse()                                                               *
*                                                                         *
**************************************************************************/
template <class ITER>
void Reverse(ITER begin, ITER end)
{
   if (begin == end) {
      return ;
   }

   ITER left  = begin;
   ITER right = begin + (end - begin) - 1;

   while (left < right) {
      dsSwap(*left, *right);
      ++left;
      --right;
   }
}

/**************************************************************************
* Substract()                                                             *
*                                                                         *
**************************************************************************/
template <class T, class CMP>
int Substract(dsVECTOR<T> & left, dsVECTOR<T> & right, const CMP & cmp)
{
   ds::Sort(left, cmp);
   ds::Sort(right, cmp);

   dsVECTOR<T> newLeft;
   newLeft.Reserve(left.Length());
   
   int count = 0;
   for (int i = 0, k = 0; i < left.Length() && k <= right.Length();) {
      if (k == right.Length()) {
         newLeft += left[i];
         ++i;
         continue;
      }

      int cmpRes = cmp.cmp(left[i], right[k]);

      if (cmpRes != 0) {
         newLeft += left[i];

         if (cmpRes < 0) {
            ++i;
         } else {
            ++k;
         }
      } else {
         ++i;
         ++k;
         ++count;
      }
   }
   newLeft.Swap(left);
   return count;
}

/*************************************************************************
* Method: <T>::Append
*
*************************************************************************/
template <class T>
void Append(dsVECTOR<T> & left, const dsVECTOR<T> & right, int start /*= 0*/, int count /*= -1*/)
{
   if (count == -1) {
      count = max(0, right.Length() - start);
   }

   left.Reserve(left.Length() + count);
   for (int i = 0; i < count; ++i) {
      left += right[start + i];
   }
}

// using memcpy
template <class T>
void AppendFast(dsVECTOR<T> & left, const dsVECTOR<T> & right, int start /*= 0*/, int count /*= -1*/)
{
   if (count == -1) {
      count = max(0, right.Length() - start);
   }

   if (count == 0) {
      return ;
   }

   STRONG_ASSERT4(start + count <= right.Length(), start, count, start + count, right.Length());

   int offset = left.Length();
   left.Resize(left.Length() + count);
   memcpy(left.Begin() + offset, right.Begin() + start, count * sizeof(T));
}

/**************************************************************************
* IsIntersect()                                                           *
*                                                                         *
**************************************************************************/
template <class T, class CMP>
bool IsIntersect(const dsVECTOR<T>& v1, const dsVECTOR<T>& v2, const CMP & cmp)
{
   /*
   If vectors length less 100, do simple search elements, else
   find sorted vector, then search elements of other vector in it.
   If no sorted vectors, sort first one.
   */
   const dsVECTOR<T>*   firstVec = NULL;
   const dsVECTOR<T>*   secondVec = NULL;
   dsVECTOR<T>          vec;
   if (IsSorted(v1, cmp)) {
      firstVec = &v1;
      secondVec = &v2;
   } else if (IsSorted(v2, cmp)) {
      firstVec = &v2;
      secondVec = &v1;
   } else if (v1.Length() < 100 && v2.Length() < 100) {
      for (int i = 0; i < v1.Length(); ++i) {
         for (int j = 0; j < v2.Length(); ++j) {
            if (cmp.cmp(v1[i], v2[j]) == 0) {
               return true;
            }
         }
      }
      return false;
   } else {
      ASSERT(FALSE);
      vec = v1;
      Sort(vec, cmp);
      firstVec = &vec;
      secondVec = &v2;
   }

   for (int i = 0; i < secondVec->Length(); ++i) {
      if (firstVec->FindSorted(secondVec->operator[](i), cmp) != -1) {
         return true;
      }
   }

   return false;
}

/*************************************************************************
* <T, V, CMP>::FindSortedFirst 
*
*************************************************************************/
template <class T, class V, class CMP>
int FindSortedFirst(const T * array, int length, const V & val, const CMP & cmp)
{
   if (length <= 0) {
      return -1;
   }

   int lo = 0;
   int hi = length - 1;

   while (hi - lo > 1) {
      const int mid = (lo + hi) / 2;

      int res = cmp.cmp(array[mid], val);
      if (res < 0) {
         lo = mid;
      } else {
         hi = mid;
      }
   }

   if (cmp.cmp(array[lo], val) == 0) {
      return lo;
   }
   if (cmp.cmp(array[hi], val) == 0) {
      return hi;
   }
   return -1;
}

/*************************************************************************
* <T, V, CMP>::FindSortedLast 
*
*************************************************************************/
template <class T, class V, class CMP>
int FindSortedLast(const T * array, int length, const V & val, const CMP & cmp)
{
   int lo = 0;
   int hi = length - 1;

   while (hi - lo > 1) {
      const int mid = (lo + hi) / 2;

      if (cmp.cmp(array[mid], val) <= 0) {
         lo = mid;
      } else {
         hi = mid;
      }
   }

   if (cmp.cmp(array[hi], val) == 0) {
      return hi;
   }
   if (cmp.cmp(array[lo], val) == 0) {
      return lo;
   }
   return -1;
}

/*************************************************************************
* <T>::Shuffle 
*
*************************************************************************/
template <class T>
void Shuffle(dsVECTOR<T> & arr)
{
   for (int i = 0; i < arr.Length(); ++i) {
      const int next = m3dRandIntMax(arr.Length() - i - 1);
      dsSwap(arr[i], arr[i + next]);
   }
}

/*************************************************************************
* Method: <T, CMP>::MergeSorted
*
*************************************************************************/
template <class T, class CMP>
void MergeSorted(dsVECTOR<T> & res, const dsVECTOR<T> & a, const dsVECTOR<T> & b, const CMP &cmp)
{
   res.Clear();
   res.Reserve(a.Length() + b.Length());

   STRONG_ASSERT(IsSorted(a));
   STRONG_ASSERT(IsSorted(b));

   const T * aaa = a.Begin();
   const T * bbb = b.Begin();

   const T * aEnd = a.End();
   const T * bEnd = b.End();

   while (aaa != aEnd && bbb != bEnd) {
      int rc = cmp.cmp(*aaa, *bbb);
      if (rc < 0) {
         res += *aaa;
         ++aaa;
      } else {
         res += *bbb;
         ++bbb;
      }
   }
   while (aaa != aEnd) {
      res += *aaa;
      ++aaa;
   }
   while (bbb != bEnd) {
      res += *bbb;
      ++bbb;
   }
}

/*************************************************************************
* Method: <T, CMP>::MergeSortedUniq
*
*************************************************************************/
template <class T, class CMP>
void MergeSortedUniq(dsVECTOR<T> & res, const dsVECTOR<T> &arr1, const dsVECTOR<T> &arr2, const CMP &cmp)
{
   STRONG_ASSERT(IsSortedUniq(arr1));
   STRONG_ASSERT(IsSortedUniq(arr2));

   res.Clear();
   res.Reserve(arr1.Length() + arr2.Length()); // TODO: we can count real amount of elements to save memory but lose performance...

   const T *First1 = arr1.Begin();
   const T *First2 = arr2.Begin();

   const T *Last1 = arr1.End();
   const T *Last2 = arr2.End();

   while (First1 < Last1 && First2 < Last2) {
      int rc = cmp.cmp(*First1, *First2);
      if (rc < 0) {
         res.PushBack(*First1);
         ++First1;
      } else if (rc > 0) {
         res.PushBack(*First2);
         ++First2;
      } else {
         res.PushBack(*First2);
         ++First1;
         ++First2;
      }
   }

   while (First1 < Last1) {
      res.PushBack(*First1);
      ++First1;
   }
   while (First2 < Last2) {
      res.PushBack(*First2);
      ++First2;
   }
}

/******************************************************************************
 * <T>::FillLinear
 *
 ******************************************************************************/
template <class T>
void FillLinear(dsVECTOR<T> & array, int count, const T & start, const T & step)
{
   array.Clear();
   array.Reserve(count);

   T cur = start;
   for (int i = 0; i < count; ++i) {
      array += cur;
      cur = cur + step;
   }
}

/******************************************************************************
* <T>::ApplyPermutation
*
******************************************************************************/
template <class T>
void ApplyPermutation(const dsVECTOR<T> & array, const dsVECTOR<int> & permutation, dsVECTOR<T> & result)
{
   result.Clear();
   result.Reserve(permutation.Length());

   for (int i = 0; i < permutation.Length(); ++i) {
      result += array[permutation[i]];
   }
}

/******************************************************************************
* <T>::ApplyPermutation
*
******************************************************************************/
template <class T>
void ApplyPermutation(dsVECTOR<T> & array, const dsVECTOR<int> & permutation)
{
   dsVECTOR<T> res;
   ds::ApplyPermutation(array, permutation, res);
   res.Swap(array);
}

/******************************************************************************
* <TYPE, CMP>::SortUsingPermutation
*
******************************************************************************/
template <class TYPE, class CMP>
inline void SortUsingPermutation(dsVECTOR<TYPE> & arr, const CMP & cmp)
{
   dsVECTOR<int> perm;
   ds::FillLinear(perm, arr.Length());
   ds::Sort(perm, cmp);
   ds::ApplyPermutation(arr, perm);
}

//
// End-of-file DS_ALGORITHM.HPP
//
